#include "stdio.h"

#define MAXVEX 9
#define MAXEDGE 15

typedef char VerTexType;
typedef int EdgeType;

typedef struct VerTex{
    VerTexType vex[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

// 对边集数组Edge结构的定义
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;

// 查找连线顶点的尾部下标
int Find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void MiniSpanTree_Kruskal(MGraph G) {
    int i,n,m;
    // 定义边集数组，edge的结构为begin，end和weight
    Edge edges[MAXEDGE];
    // 用于判断边与边是否形成了环路（此处太妙了）
    int parent[MAXVEX];

    // 此处省略将邻接矩阵G转化为边集数组Edges并按权由小到大排序的代码

    // 初始化数组值为0
    for(i = 0; i < G.numNodes; i++) {
        parent[i] = 0;
    }
    // 循环每一条边
    for(i = 0; i < G.numEdges; i++) {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        // 若n!=m说明此此边没有与现有的生成树形成环路
        if(n != m) {
            // 将此边的结尾顶点放入以起点为下标的parent中，表示此顶点已经在生成树的集合中
            parent[n] = m;
            printf("(%d,%d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}
